package binarytree

import "fmt"

// 自己实现的 BY LCJ

// 前序遍历 迭代法
func IterateTraversalPreorder(root *TreeNode) []int {
	// 定义一个栈
	stack := []*TreeNode{}
	// 遍历得到的结果
	results := []int{}
	// 前序遍历的迭代法的基本逻辑是：
	// 为了实现 中左右 的遍历顺序，
	// 先将中节点入栈，
	// 从栈中取出节点，取值加入results, 然后先将该节点的右节点入栈，然后再将左结点入栈，
	// 剩下的操作就是循环上边的出栈节点、取值、入栈右节点、入栈左结点...直到栈空了。
	stack = append(stack, root)
	for len(stack) > 0 {
		// 出栈一个节点
		item := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		results = append(results, item.Val)
		// 右节点入栈
		if item.Right != nil {
			stack = append(stack, item.Right)
		}
		// 左结点入栈
		if item.Left != nil {
			stack = append(stack, item.Left)
		}
	}
	return results
}

// 中序遍历 迭代法
func IterateTraversalInorder(root *TreeNode) []int {
	// 中序遍历无法复用前序遍历的逻辑
	// 中序遍历顺序是 左中右
	// 但是我们从root拿到的其实首先就是中节点，为了先遍历左结点，我们需要先将中节点临时存储起来
	// 然后去遍历他的左节点，而且遍历到也是临时存储起来，直到左结点为空了
	// 这时候我们开始取出来，并且输出，然后在抛弃之前，遍历右节点，右节点的逻辑也是相同的
	// 即：先临时存储，然后碰到左节点一路下去直到左结点为空
	// 但是这样面临一个问题：
	//   如果只用一个栈stack的话，当回溯回来的时候，会循环查询左子节点，为了避免这个问题，我们应该将待回溯的节点放到新的栈stackNoNeedLeft中，
	//   这些新栈中的数据就不进行左子节点的查询了。
	//   如此一来我们发现，其实stack栈其实始终只有一个中节点的存在，有且只有一个，所以其实我们不需要栈，直接用一个临时指针指向就可以了。
	tmpNode := root
	//stack := []*TreeNode{}
	//stack = append(stack, root) // 用tmpNode代替stack栈

	stackNoNeedLeft := []*TreeNode{} // 进入该栈的节点就不需要进行左子节点的遍历了，因为是回溯过程
	results := []int{}
	// for len(stack) > 0 || len(stackNoNeedLeft) > 0 {
	for tmpNode != nil || len(stackNoNeedLeft) > 0 {
		// 遍历左结点直到为空
		for tmpNode != nil {
			stackNoNeedLeft = append(stackNoNeedLeft, tmpNode) // 其实都是以中节点的身份进去的
			tmpNode = tmpNode.Left
		}

		// 执行到这里说明左子节点已空，开始出栈进行输出，同时开始搞右子节点
		if len(stackNoNeedLeft) > 0 {
			outputNode := stackNoNeedLeft[len(stackNoNeedLeft)-1]
			results = append(results, outputNode.Val)
			stackNoNeedLeft = stackNoNeedLeft[:len(stackNoNeedLeft)-1]
			tmpNode = outputNode.Right
		}
	}

	return results
}

// 后序遍历 迭代法
func IterateTraversalPostorder(root *TreeNode) []int {
	if root == nil {
		return nil
	}
	// 思路：后序的遍历顺序是 左右中
	// 和中序面临的相同的问题是我们首先拿到的root是一个中节点，但是我们要输出的是左节点，
	// 所以我们要暂时将他入栈stack存起来，然后遍历他的左子节点和右子节点，
	// 遍历的时候我们应该首先将其右子节点入栈，临时存起来，然后再处理左子节点，
	// 重复这个过程，直到左子节点被穷尽了即可。
	// 和中序一样，如果我们在穷尽之后开始出栈并输出，过程中回溯遇到的节点如果重复这个操作就造成死循环了，
	// 所以为了防止死循环，我们需要处理一下，
	// 此时我们面临的问题比中序要更为麻烦，
	// 因为理论上中节点是不需要再遍历任何左右子节点了，但是右节点还要继续执行左右的操作
	// 所以针对右节点我们还应该把其放入stack中
	// 但是这样就导致了两个栈同时存在数据了，该如何并行进行输出呢？
	// ------- 还是不可行，换一个思路
	// 仍然只遍历左子节点，并将遍历到的左节点放入stack之中，直到左节点为空
	// 然后回溯，回溯的时候也不能直接出栈，
	// 而是基于栈顶元素去访问他的右子节点，如果右子节点为空，那么就可以把他出栈了，
	// 如果右子节点不是空，那么右子节点入栈，然后继续遍历左子节点，直到为空
	// 但是这仍然存在一个问题，就是中节点会应为左右的回溯而被访问两遍，第一遍的时候我们是为了访问右子节点，
	// 第二遍的时候理论上我们就应该出栈了，因为这是右子节点回溯导致的，
	// 怎么确定是第二遍回溯，或者说怎么确定是右子节点的回溯，就可以保证我们顺利的弹出了
	// 这也好办！！我们记录上一个弹出的元素，如果这个弹出的元素恰好是当前栈顶元素的右子节点的话，则弹出当前栈顶元素即可。
	stack := []*TreeNode{}
	result := []int{}
	var lastPopItem *TreeNode

	tmpNode := root
	stack = append(stack, tmpNode)
	for tmpNode.Left != nil {
		stack = append(stack, tmpNode.Left)
		tmpNode = tmpNode.Left
	}
	fmt.Println("collectAllLeft stack:", stack)
	for len(stack) > 0 {
		// 栈顶元素有三种处理方式
		// 0. 如果他的右子节点是空的，则直接出栈。
		// 1. 当上一个出栈元素不是他的右子节点的时候，访问他的右子节点，并收集左子树。
		// 2. 当上一个出站元素是他的右子节点的时候，直接出站
		top := stack[len(stack)-1]
		if top.Right == nil {
			result = append(result, top.Val)
			lastPopItem = top
			stack = stack[:len(stack)-1]
		} else if lastPopItem == top.Right {
			result = append(result, top.Val)
			lastPopItem = top
			stack = stack[:len(stack)-1]
		} else {
			tmpNode := top.Right
			stack = append(stack, tmpNode)
			for tmpNode.Left != nil {
				stack = append(stack, tmpNode.Left)
				tmpNode = tmpNode.Left
			}
		}
	}

	return result
}
